package com.sakura.二叉树;

public class Code654_最大二叉树 {

    
      // Definition for a binary tree node.
      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return buildTree(nums, 0, nums.length - 1);
    }

    public TreeNode buildTree(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }
        int rootI = start;
        for (int i = start + 1; i <= end; i++) {
            if (nums[i] > nums[rootI]) {
                rootI = i;
            }
        }
        TreeNode root = new TreeNode(nums[rootI]);
        root.left = buildTree(nums, start, rootI - 1);
        root.right = buildTree(nums, rootI + 1, end);
        return root;
    }
}
